package goalgorithm

/*
	二叉树
	用int作为树的索引
	由于删除时，需要提供索引值，所以在插入时，索引值必须不一样，插入时的值并不作为0当数据一样的，放到左侧
	支持删除任意一个节点
*/
// 参考:https://github.com/gohouse/dataStructure/blob/master/tree/binarySearchTree/BinaryTree.go
type IBinaryTree interface {
	// 插入
	Insert(i int) bool
	// 查找
	Search(i int) *BinaryTree
	// 最大
	MaxNode() *BinaryTree
	// 最小
	MinNode() *BinaryTree
	// 前序遍历
	PreOrder() []int
	// 中序遍历
	InOrder() []int
	// 后续遍历
	PostOrder() []int
	// 删除
	Delete(i int) bool
	// 最大深度
	Depth() int
	// 最小深度
	DepthMin() int
	// 宽度

	//3. 前序遍历，中序遍历，后序遍历
	//4.分层遍历二叉树（按层次从上往下，从左往右）
	//5. 将二叉查找树变为有序的双向链表
	//6. 求二叉树第K层的节点个数
	//7. 求二叉树中叶子节点的个数
	//8. 判断两棵二叉树是否结构相同
	//9. 判断二叉树是不是平衡二叉树
	//10. 求二叉树的镜像
	//11. 求二叉树中两个节点的最低公共祖先节点
	//12. 求二叉树中节点的最大距离
	//13. 由前序遍历序列和中序遍历序列重建二叉树
	//14.判断二叉树是不是完全二叉树
}

type BinaryTree struct {
	Index            int
	Data             interface{}
	Left, Right, Top *BinaryTree
}

//var _ IBinaryTree = &BinaryTree{}

func New() *BinaryTree {
	return new(BinaryTree)
}

func (b *BinaryTree) Depth() int {
	if b.Data == 0 {
		return 0
	}

	return 1 + max(b.Left.Depth(), b.Right.Depth())
}

func (b *BinaryTree) DepthMin() int {
	if b.Data == 0 {
		return 0
	}

	return 1 + min(b.Left.Depth(), b.Right.Depth())
}

func max(a, b int) int {
	if a >= b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

// 插入一个数据
func (b *BinaryTree) Insert(i int, d interface{}) bool {
	if b.Index > i {
		if b.Left == nil {
			b.Left = &BinaryTree{Index: i, Data: d}
			return true
		} else {
			b.Left.Insert(i, d)
		}
	} else {
		if b.Right == nil {
			b.Right = &BinaryTree{Index: i, Data: d}
			return true
		} else {
			b.Right.Insert(i, d)
		}
	}
	return false
}

// 查找指定索引
func (b *BinaryTree) Search(i int) *BinaryTree {
	if b.Data == i {
		return b
	}
	if b.Index > i {
		if b.Left == nil {
			return nil
		}
		return b.Left.Search(i)
	} else {
		if b.Right == nil {
			return nil
		}
		return b.Right.Search(i)
	}
}

// 最大值
func (b *BinaryTree) MaxNode() *BinaryTree {
	if b.Right == nil {
		return b
	} else {
		return b.Right.MaxNode()
	}
}

// 最小值
func (b *BinaryTree) MinNode() *BinaryTree {
	if b.Left == nil {
		return b
	} else {
		return b.Left.MinNode()
	}
}

func (b *BinaryTree) PreOrder() []interface{} {
	var res []interface{}
	if b.Data != 0 {
		//fmt.Printf("%v ", b.Data)
		res = append(res, b)
		res = append(res, b.Left.PreOrder()...)
		res = append(res, b.Right.PreOrder()...)
	}

	return res
}

func (b *BinaryTree) InOrder() []interface{} {
	var res []interface{}
	if b.Data != 0 {
		res = append(res, b.Left.PreOrder()...)
		//fmt.Printf("%v ", b.Data)
		res = append(res, b)
		res = append(res, b.Right.PreOrder()...)
	}
	return res
}

func (b *BinaryTree) PostOrder() []interface{} {
	var res []interface{}
	if b.Data != 0 {
		res = append(res, b.Left.PreOrder()...)
		res = append(res, b.Right.PreOrder()...)
		//fmt.Printf("%v ", b.Data)
		res = append(res, b)
	}
	return res
}

// 删除指定节点，需要注意
func (b *BinaryTree) DeleteForNode(findTreeNode *BinaryTree) bool {
	if findTreeNode.Data == 0 {
		return false
	}

	// 根据不同情况删除, 1:没有子节点; 2:有一个子节点; 3:有两个子节点
	if findTreeNode.Left.Data == 0 && findTreeNode.Right.Data != 0 {
		// 只有右节点,当前节点替换为右节点,然后销毁右节点
		findTreeNode.fillByTreeNode(findTreeNode.Right)
		findTreeNode.Right = nil
	} else if findTreeNode.Left.Data != 0 && findTreeNode.Right.Data == 0 {
		// 只有左节点,当前节点替换为右节点,然后销毁左节点
		findTreeNode.fillByTreeNode(findTreeNode.Left)
		findTreeNode.Left = nil
	} else { // 两个子节点都存在
		// 查找右子树中最小的节点
		top := findTreeNode.Top
		if findTreeNode.Right == nil {
			if top != nil {
				if top.Left == findTreeNode {
					top.Left = nil
				} else {
					top.Right = nil
				}
			}
		} else {
			rightMin := findTreeNode.Right.MinNode()
			rightMin.Left = findTreeNode.Left
			if top != nil {
				if top.Left == findTreeNode {
					top.Left = findTreeNode.Right
				} else {
					top.Right = findTreeNode.Right
				}
				findTreeNode.Right.Top = top
			}
		}
	}
	return true
}

// 注意，只删除一个最近等于这个值的
func (b *BinaryTree) Delete(i int) bool {
	// 查找
	return b.DeleteForNode(b.Search(i))
}

/*
// 销毁叶子节点
func (b *BinaryTree) clear() {
	b.Data = 0
	b.Left = nil
	b.Right = nil
}*/

// 填充为另一个节点的值
func (b *BinaryTree) fillByTreeNode(node *BinaryTree) {
	b.Data = node.Data
	b.Left = node.Left
	b.Right = node.Right
}
